[이코테 - DP]_바닥공사

문제 설명

1x2, 2x1, 2x2 로 이루어진 덮개를 이용해서 바닥을 채우는 모든 경우의 수를 구하라.

My Solution

n = int(input())

result = 0

dp = [0] * 1001
dp[1] = 1
dp[2] = 2

for i in range(3, n + 1):
    dp[i] = (dp[i - 1] * 2 + dp[i - 2]) % 796796

print(dp[n])

문제 풀이

이 문제도 점화식만 잘 세우면 해결됩니다. 세로의 길이는 고정되어 있으므로, 가로의 길이만 고려하면 됩니다.

• 가로의 길이가 n-1 크기만큼 채워진 경우, 2x1 덮개 하나로만 채울 수 있습니다.
• 가로의 길이가 n-2 크기만큼 채워진 경우, 1x2 덮개 2개를 넣는 경우와 2x2 덮개 1개를 넣는 경우 총 2개의 경우가 생깁니다.
• dp 테이블의 1과 2번째 초기값을 설정해주고, 점화식을 활용하여 for 반복문을 돌려주었습니다.